#ifndef _MUNIX_skip_list_H
#define	_MUNIX_skip_list_H
/******************************************************************************
 ** Name: skip_list.cpp                                                        **
 ** Description: skip_list datastructure implementation.                       **
 **                                                                           **
 ** Open Source Initiative (OSI) Approved License                             **
 **                                                                           **
 ** The contents of this file are subject to the terms of the                 **
 ** Common Development and Distribution License, Version 1.0 only             **
 ** (the "License").  You may not use this file except in compliance          **
 ** with the License.                                                         **
 **                                                                           **
 ** You can find a copy of the license in the license.txt within              **
 ** this distribution or at http://www.munixos.net/licensing.                 **
 ** Software distributed under the License is distributed on an "AS IS"       **
 ** basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.           **
 ** See the License for the specific language governing permissions           **
 ** and limitations under the License.                                        **
 **                                                                           **
 ** When distributing Covered Code, include this CDDL header in each          **
 ** file and include the License file at $HOME/license.txt.                   **
 ** If applicable, add the following below this header, with the indicated    **
 ** fields enclosed by brackets "[]" replaced with your own identifying       **
 ** information: Portions Copyright [yyyy] [name of copyright owner]          **
 **                                                                           **
 **                                                                           **
 ** Copyright (c) 2009-2010  Barry Gian James.                                **
 ** All rights reserved.                                                      **
 **                                                                           **
 ** Ref: $Id$
 ******************************************************************************/
// $Id$

// TODO implement research paper methods on skip_list for best performance
// Choose the i'th final to be i/2 + 1
#define DEFAULT_MAX_skip_listS 11
#define RAND_MAX 100

template<class T>
class skip_list {
template<class T>
	struct node
	{
		node() { lvl_ = 0; next_ = up_ = down_ = 0; }
		node(const T & t) { value_ = t; lvl_ = 0; next_ = up_ = down_ = 0; }

		node * next(uint8_t i);
		T * data() { return value_; }

		T   value_;
		uint8_t	lvl_;
		node * next_, * up_, * down_;
	};
public:
    skip_list(uint8_t maxl, uint8_t prob);
    skip_list() : skip_list(DEFAULT_MAX_skip_listS, 50) { }
    skip_list(const skip_list& orig) = delete;
    virtual ~skip_list();

    skip_list<T> & operator = (const skip_list<T> &);

    void    insert(const T & val);
    T       find(const T &);
    void    remove(const T &);
    bool    cointoss();
    uint8_t   new_rand_lvl() const;

    node<T>	head(uint8_t i) { return head_[i]; }
    
private:
    void		_copylist(const skip_list<T>&);
    void		_check_invariant() const;

    uint8_t   	currLevel_;
    uint8_t    	prob_;
    uint8_t		k_;
    uint8_t		maxLevel_;


    node<T> ** head_;
    node<T> ** tail_;	// maybe update
};

template<class T>
void
skip_list<T>::_check_invariant() const
{

}

template<class T>
void
skip_list<T>::insert(const T & val)
{

}

template<class T>
T
skip_list<T>::find(const T & t)
{

}

template<class T>
void
skip_list<T>::remove(const T & t)
{

}

template<class T>
bool
skip_list<T>::cointoss()
{

}

template<class T>
uint8_t
skip_list<T>::new_rand_lvl() const
{

}

template<class T>
skip_list<T> &
skip_list<T>::operator =(const skip_list<T> & s)
{
	for(skip_list::node<T> * sc = head_[0]; sc;)
	{
		skip_list::node<T> * nxt = sc->next(0);
		delete sc;
		sc = nxt;
	}
	_copylist(s);
}

template<class T>
skip_list<T>::~skip_list()
{

}

template<class T>
skip_list<T>::skip_list(uint8_t maxl, uint8_t prob)
: maxLevel_(maxl), prob_(prob)
{
	currLevel_ = k_ = 0;
	head_ = tail_ = 0;
}


#endif	/* _MUNIX_skip_list_H */

